Non-patent literature 1 discloses a conventional message-recoverable signature technique. This technique uses the random oracle model to guarantee security. In the following, this technique will be generally described.
According to this technique, the following conditions are assumed.message m∈{0,1}k2 function F1: {0,1}k2→{0,1}k1 function F2: {0,1}k1→{0,1}k2 function H: {0,1}k1+k2→{0,1}k 
E: elliptic curve defined on a finite field Fq 
p: prime number that satisfies p·R=O, where R represents a point on the elliptic curve E, and O represents a point at infinity
G1: points in a subset of the elliptic curve E, where order of the subset is pW∈Z/pZsecret key: x∈Z/pZpublic key: (Fq,E,G1,Y)(Y=−x·G1(∈E)){0, 1}δ represents δ-bit data, and {0, 1}δ→{0, 1}ε represents a function of mapping of δ-bit data to ε-bit data.
<Signature Generation>
Signature generation is performed as follows. Note that Rx represents the x coordinate of the point R∈E, and (+) represents an exclusive OR operator.m′=F1(m)|(F2(F1(m))(+)m)  (1)Rx=(w·G1)x r=R(+)m′  (2)c=H(r)z=w+c·x mod p signature σ=(r,z)
<Signature Verification>
Signature verification is performed as follows. Note that [m′]k1 represents the leading k1 bits of m′, and [m]k2 represents the remaining k2 bits of m′.m′=r(+)(z·G1+H(r)·Y)x m=[m′]k2(+)F2([m′]k1)If [m′]k1=F1(m), the verification is passed.    Non-patent literature 1: Masayuki Abe, Tatsuaki Okamoto, “A Signature Scheme with Message Recovery as Secure as Discrete Logarithm,” ASIACRYPT 1999, pp. 378-389